package com.jonlandrum.collections.BinarySearchTree.SplayTree;

import com.jonlandrum.collections.BinarySearchTree.LinkedBinarySearchNode;
import org.junit.Test;

import java.util.NoSuchElementException;

import static org.junit.Assert.assertEquals;

public class LinkedSplayTreeTest {
    @Test
    public void testInsert_InsertionPointGreaterThanElement() {
        LinkedSplayTree<String> testInsert = new LinkedSplayTree<>();
        testInsert.insert("10");
        assertEquals("10", testInsert.getRoot().toString());
        testInsert.insert(new LinkedBinarySearchNode<>("1"));
        assertEquals("1", testInsert.getRoot().toString());
    }

    @Test
    public void testInsert_InsertionPointLessThanElement() {
        LinkedSplayTree<String> testInsert = new LinkedSplayTree<>();
        testInsert.insert("1");
        assertEquals("1", testInsert.getRoot().toString());
        testInsert.insert(new LinkedBinarySearchNode<>("10"));
        assertEquals("10", testInsert.getRoot().toString());
    }

    @Test
    public void testDelete_TargetIsLeftLeaf() {
        LinkedSplayTree<Integer> testDelete = new LinkedSplayTree<>();
        testDelete.insert(10);
        testDelete.insert(80);
        testDelete.insert(70);
        testDelete.insert(75);
        testDelete.delete(10);
        assertEquals("70", testDelete.getRoot().toString());
    }

    @Test
    public void testDelete_TargetIsRightLeaf() {
        LinkedSplayTree<Integer> testDelete = new LinkedSplayTree<>();
        testDelete.insert(10);
        testDelete.insert(80);
        testDelete.insert(70);
        testDelete.insert(75);
        testDelete.delete(80);
        assertEquals("75", testDelete.getRoot().toString());
    }

    @Test
    public void testDelete_TargetIsRoot() {
        LinkedSplayTree<Integer> testDelete = new LinkedSplayTree<>();
        testDelete.insert(10);
        testDelete.insert(80);
        testDelete.insert(70);
        testDelete.insert(75);
        testDelete.delete(75);
        assertEquals("80", testDelete.getRoot().toString());
    }

    @Test
    public void testDelete_TargetIsInternalNode() {
        LinkedSplayTree<Integer> testDelete = new LinkedSplayTree<>();
        testDelete.insert(10);
        testDelete.insert(80);
        testDelete.insert(70);
        testDelete.insert(75);
        testDelete.delete(70);
        assertEquals("75", testDelete.getRoot().toString());
    }

    @Test(expected = NoSuchElementException.class)
    public void testSearchEmptyTree() {
        LinkedSplayTree<Integer> testSearch = new LinkedSplayTree<>();
        testSearch.search(1);
    }

    @Test(expected = NoSuchElementException.class)
    public void testSearchNonEmptyTree_NonExistingElement() {
        LinkedSplayTree<Integer> testSearch = new LinkedSplayTree<>();
        testSearch.insert(1);
        testSearch.search(10);
    }

    @Test
    public void testSearchNonEmptyTree_ExistingElement_TargetIsRoot() {
        LinkedSplayTree<Integer> testSearch = new LinkedSplayTree<>();
        testSearch.insert(1);
        assertEquals("1", testSearch.getRoot().toString());
    }

    @Test
    public void testSearchNonEmptyTree_ExistingElement_TargetIsInternalNode() {
        LinkedSplayTree<Integer> testSearch = new LinkedSplayTree<>();
        testSearch.insert(10);
        testSearch.insert(80);
        testSearch.insert(70);
        testSearch.insert(75);
        assertEquals("75", testSearch.getRoot().toString());
        testSearch.search(70);
        assertEquals("70", testSearch.getRoot().toString());
    }

    @Test
    public void testSearchNonEmptyTree_ExistingElement_TargetIsLeaf() {
        LinkedSplayTree<Integer> testSearch = new LinkedSplayTree<>();
        testSearch.insert(10);
        testSearch.insert(80);
        testSearch.insert(70);
        testSearch.insert(75);
        testSearch.search(10);
        assertEquals("10", testSearch.getRoot().toString());
    }
}